package arithmetic;

/**
 * @author Ajie
 * @date 4/14/21
 * @function 53. 最大子序和
 * 简单  todo 非常重要。的一道题。暴力求解。
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * <p>
 * <p>
 * https://leetcode-cn.com/problems/maximum-subarray/
 * <p>
 * 1.读题
 * 子序列，
 * 连续。
 * 最大值。
 * <p>
 * 2.解题
 * 暴力法
 * 所有子序列的可能。
 * <p>
 * 动态规划
 * 递推
 * 状态定义。
 * <p>
 * 3.coding
 * 极端值的思考
 * <p>
 * 4.test
 */
public class A_053_MaximumSubarray {
    public static void main(String[] args) {

        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
//        int i = maxSubArray(nums);
        int i = maxSubArrayDP(nums);
        System.out.println("result:" + i);
    }

    //暴力法

    /**
     * 外层n
     * 每次取到n
     * 内层 j
     * 每次 j->n
     */
    private static int maxSubArray(int[] nums) {
        if (nums == null || nums.length < 1) {
            return Integer.MIN_VALUE;
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) { //设置起始位置  i  0->n
            int count = 0;//因为 0+其他元素 没有影响。
            for (int j = i; j < nums.length; j++) {//设置结束为止  j i->n
                //i    0    1    2    3 ...  n
                //j集合 0-n  1-n  2-n  3-n    n
                //0-1 在哪？？
                //在0-n 的子集里面。0-n 计算： 0-1 ，0-2，0-3，0-4，每一个存的是临时变量。只保存了 值，当0-1 大时，res = count>res?count:res;

                count +=nums[j];

                res = count>res?count:res;

            }
        }
        return res;
    }


    //动态规划
    /**
     * 
     * 递推
     * 最后一个数包含i
     * 
     * dp[i] = max(dp[i-1]+nums[i],nums[i])
     * 状态定义
     * @return
     */
    private static int maxSubArrayDP(int[] nums) {
        if (nums == null || nums.length < 1) {
            return Integer.MIN_VALUE;
        }
        if (nums.length==1){
            return nums[0];
        }
        
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        
        int res = dp[0];

        for (int i = 1; i < nums.length; i++) {
            int temp = dp[i - 1] + nums[i];
            dp[i] = temp>nums[i]?temp:nums[i];
            if (dp[i]>res){
                res = dp[i];
            }
        }
        return res;
    }
}
